Corelab Seminar
2018-2019
Alkis Kalabasis
Sorting from Noisy Information
Abstract.
Η παρουσίαση αφορά το learning πρόβλημα όπου προσπαθούμε να μάθουμε μία κρυφή διάταξη π πάνω σε n αντικείμενα και βασίζεται στο paper "Sorting from Noisy Information" των Braverman και Mosell ( https://arxiv.org/abs/0910.1191 ). Τα δείγματα μας περιέχουν θόρυβο και παράγονται σε εξάρτηση με την κρυφή διάταξη π. Στόχος μας είναι, δοθέντων των δειγμάτων, να βρούμε μία διάταξη που να είναι πολύ κοντά στην αρχική. Το αρχικό πρόβλημα διακρίνεται σε δύο ξεχωριστά προβλήματα ανάλογα με τον τύπο των δειγμάτων (noisy orders - noisy comparisons). Σε κάθε μία από τις δύο περιπτώσεις, παρέχονται πολυωνυμικού χρόνου αλγόριθμοι που λύνουν το πρόβλημα με μεγάλη πιθανότητα.